# Given a collection of intervals, merge all overlapping intervals.
#
# Example 1:
#
# Input: [[1,3],[2,6],[8,10],[15,18]]
# Output: [[1,6],[8,10],[15,18]]
# Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].
# Example 2:
#
# Input: [[1,4],[4,5]]
# Output: [[1,5]]
# Explanation: Intervals [1,4] and [4,5] are considered overlapping.


class Solution:
    def merge(self, intervals):
        intervals.sort(key=lambda x: x[0])
        res = []

        for interval in intervals:

            if not res or res[-1][1] < interval[0]:
                res.append(interval)

            else:
                res[-1][1] = max(res[-1][1], interval[1])

        return res
